package com.bupt.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import com.bupt.datastruct.TreeNode;

public class DFSTraverseProblem {
	/**
	 * 二叉树从根节点到叶节点的所有路径
	 * @param root
	 * @return
	 */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<String>();
        if(root == null) return list;
        DFSTree(root,"", list);
        return list;
    }
    public void DFSTree(TreeNode node,String str,List<String> list){
    	if(node.left != null){
    		DFSTree(node.left,str + node.val +"->",list);
    	}else if(node.right != null){
    		DFSTree(node.right,str + node.val +"->",list);
    	}else{
    		list.add(str+node.val);
    	}
    }
    /**
     * 
     * @param beginWord
     * @param endWord
     * @param wordDict
     * @return
     */
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        int path = 0, max = wordDict.size() + 2;
        Set<String> visited = new HashSet<String>();
        max = DFSLadder(beginWord, endWord, wordDict, visited,path, max);
        return max;
    }
    public int DFSLadder(String currentWord,String endWord,Set<String> wordDict,Set<String> visited,int length,int max){
    	if(currentWord.equals(endWord) && length < max){
    		max = length;
    		return max;
    	}else if(length >= max){
    		visited.remove(currentWord);
    		return max;	
    	}else{
    		Set<String> preSet = new HashSet<String>();
    		String next = nextUnused(currentWord, wordDict, visited, preSet);
    		visited.add(next);
    		max = DFSLadder(next, endWord, wordDict, visited, length+1, max);
    		return max;
    	}
    }
    
    public List<List<String>> buildMap(Set<String> wordDict){
    	List<List<String>> map = new ArrayList<List<String>>();
    	Iterator<String> outIt = wordDict.iterator();
    	while(outIt.hasNext()){
    		String w = outIt.next();
    		List<String> list = new ArrayList<String>();
    		list.add(w);
    		Iterator<String> inIt = wordDict.iterator();
    		while(inIt.hasNext()){
    			String t = inIt.next();
    			if(t.equals(w))continue;
    			int diff = 0;
    			for(int i = 0; i< t.length();i++){
    				if(t.charAt(i) != w.charAt(i)) diff++;
    				if(diff >= 2) break;
    			}
    			if(diff == 1) list.add(t);
    		}
    		map.add(list);
    	}
    	return map;
    }
    
    public String nextUnused(String currentWord,Set<String> wordDict,Set<String> visited,Set<String> preSet){
    	Iterator<String> it = wordDict.iterator();
    	String next = null;
    	while(it.hasNext()){
    		String w = it.next();
    		if(visited.contains(w) || preSet.contains(w)) continue;
    		int diff = 0;
    		for(int i= 0; i< w.length();i++){
    			if(w.charAt(i) != currentWord.charAt(i)) diff++;
    			if(diff >= 2) break;
    		}
    		if(diff == 1) {
    			preSet.add(w);
    			next = w;
    			break;
    		}
    	}
    	return next;
    }
}





